\chapter{Стандартная библиотека}

\section{Лекция 21.02.2012. Последовательные контейнеры}

\subsection{Из истории стандартной библиотеки}

Для начала, термин STL чисто исторический, в стандарте нет упоминаний об STL. Первая разработка принадлежит компании HP, обычно ее связывают с именем
Алексея Степанова. В какой-то момент эта библиотека была стандартизована и стала частью стандарта C++, но ее до сих пор называют STL.

Стандарт не специализирует реализацию библиотеки, а описывает только сигнатуры методов и время их работы, описания классов, поэтому существует несколько
реализаций STL, например, от Microsoft, Intel. Немного особняком стоит библиотека STLPort, которая является быстро развиваемой, стандартизированной и
портируемой реализацией стандартной библиотеки шаблонов.

\paragraph{Основные компоненты стандартной библиотеки:}
\begin{itemize}
\item Контейнеры (ассоциативные и последовательные)

\item Итераторы и адаптеры

\item Алгоритмы
\end{itemize}

\subsection{Последовательные контейнры}

Суть - все элементы контейнера линейно-упорядочены, относительно добавления элементов в конец контейнера, т. е. если добавляем элементы в конец контейнера,
то мы сможем обращаться к ним последовательно в порядке добавления.

Контейнеры стандартной библиотеки:

\begin{itemize}
\item vector, объявлен в файле <vector>. Является реализацией расширяющегося массива. Бычтрые операции: обращение по индексу ($[i]$), добавление элемента в конец и
удаление из конца ($push\_back$ и $pop\_back$). Вектор позволяет организовать некоторую совместимость с $c-style$ массивами, вот пример:
\begin{lstlisting}
void f(int *m, size_t size) {
//something operation with c-style array
}
//call f() with std::vector m;
f(&m[0], m.size());
\end{lstlisting}
это работает так как гарантируется условие, что внутри вектора все элементы располагаются последовательно, но контроля за границами уже не будет, так что
одна надежда на правильную работу функции f. Так же плохой идеей будет вызов delete[] для аргумента в функции f, если такое произойдет, скорее всего будет получена
ошибка времени выполнения.

\item deque, объявлен в файле <deque>. Является реализацией двусторонней очереди (как правило реализуется в виде двусвязного списка массивов, является промежуточным
этапом между vector и list относительно операции добавления в начало, которая в list выполняется за $O\left(1\right)$, а в vector за $O\left(n\right)$). Быстрые
операции: обращение по индексу ($[i]$), добавление в начало и конец и удаление из начала и конца ($push\_back$, $pop\_back$, $push\_front$ и $pop\_front$)

\item list, объявлен в файле <list>. Двусвязный список. Быстрые операции: вставка и удаление элемента в позицию указанную итератором ($insert$ и $erase$). Со списками
в стандрате есть тонокость, говорится, что либо $size$ либо трехитераторный $insert$ работают быстро, как правило это $size$. Что такое трехитераторная вставка?
Выделение участка указанного двумя итераторами из списка, затем вставка в другое место, указанное третим итератором, понятно, что сама операция вырезки и вставки
осуществима за константу, но размер вырезанного участка неизвестен и его приходится считать, поэтому работает операция не так быстро, если хранится размер и его
нужно поддерживать, с другой стороны, если мы каждый раз заново считаем размер списка, такую операцию можно осуществить за константное время, но вычисление размера
приходится потратить линейное время.

\item string и wstring, объявлен в файле <string>. Тут все довольно очевидно, это представление строки, как реализовано это представление в целом не определено.
Быстрые операции: в целом как у класса vector.
\end{itemize}

\subsection{vector}

Все стандратные контейнеры лежат в простанстве имен std со всеми вытекающими. vector имеет два различных размера: size и capacity, и связь между ними определяется
соотношением $size \le capacity$. Вот небольшой пример:
\begin{lstlisting}
std::vector<int> m;
for (size_t i = 0; i != 100; ++i)
	m.push_back(i);
\end{lstlisting}
после выполнения этого кода $m.size() == 100$, в то время как $m.capacisty()$ точно не известен. Т. е. capacity - физический размер массива, а size количество
элементов в векторе, соответственно существует две операции для указания size и capacity:
\begin{lstlisting}
m.reserve(100); //(1)
m.resize(100); //(2)
\end{lstlisting}
в (1) резервируем capacity, а в (2) создаем 100 объектов, в случае простых типов это не очень важно, но для вектора объектов, в первом случае не будет вызван
конструктор, а во втором будет вызваны 100 констукторов, и кроме того $push\_back$ добавит в контейнер 101-ый элемент, даже если раньше элементы не добавлялись.

\paragraph{Требования к элементам контейнеров:} Не каждый объект может храниться в контейнере, к объектам предъявляются следующие требования:
\begin{itemize}
\item Assignable (должен быть оператор присваивания)

\item Copy constructable (должен быть конструктор копирования)

\item Естественная семантика операций (будет плохо, если ваш конструктор копирования на самом деле не копирует, а оператор присваивания не присваивает)
\end{itemize}

\paragraph{Примечание:} можно указать размер size сразу в констукторе, а также задать значение по-умолчанию для элементов контейнера:
\begin{lstlisting}
std::vector<int> m(100, 7);
\end{lstlisting}

\paragraph{Полезные функции и правила использования:}
\begin{itemize}
\item функция isempty улучшает читаемость кода

\item функция clear очищает содержимое контейнера (вызывает деструкторы), обычно она не должна освобождать память, аналогично при операции resize, например:
\begin{lstlisting}
m.resize(100000);
\\doing something
m.resize(2);
\\what is value of m.capacity()??
\end{lstlisting}
получаем, что память не освобождается, так сделано, чтобы не было неявных перераспределений памяти, как ее удалить в этом случае? Делаем, например так:
\begin{lstlisting}
std::vector<int>().swap(m);
\end{lstlisting}
т. е. создаем временный объект, который будет уничтожен в конце строки, этот объект имеет небольшой capacity, swap поменяет наш текущий объект с временным и наш
большой буфер уйдет временному объекту и удалится вместе с ним.

\item Не стоит обращаться к элементам вектора по указателю на элемент, так как в случае перевыделения памяти получаем, что указатель потеряет валидность, но если
таки вам это понадобилось, capacity как раз и существует, чтобы регулировать количество перевыделений, т. е. задайте его большим.
\end{itemize}

\subsection{list}

Использование list в целом похоже на использование вектора, но у него нет resize и понятия capacity:
\begin{lstlisting}
std::list<int> l;
l.push_back(2);
l.push_front(1);
for (size_t i = 0; i != 100; ++i)
	i.push_back(i);
\end{lstlisting}
В случае списков не очень понятно, как перебирать (или еще хуже удалять) элементы списка, самый очевидный способ перебор по индексу:
\begin{lstlisting}
for (size_t i = 0; i < l.size(); ++i)
	l[i] \\doing something
\end{lstlisting}
но обращение к элементу не является быстрой операцией для списка, что вызывает проблемы, так как очевидно, что можно перебрать элементы гораздо быстрее, и тут
мы приходим к понятию итератора, пример:
\begin{lstlisting}
for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
	*it \\doing something
\end{lstlisting}
т. е. итератор некоторого рода указатель на элемент списка, и код выше предпочтительнее, так как он будет работать для всех контейнеров (итераторы есть для всех
последовательных контейнеров), т. е. для вектора можно было сделать также. Операции удаления или добавления в середину реализуются с помощью итераторов. Для класса
list вообще трудно представить работу без итераторов (в отличие от вектора), кроме того для итераторов критично использовать именно $!=$ при проверке условия цикла,
так как сравнение двух итераторов не вполне понятная вещь в общем (например, сравнение двух итераторов на позиции списка). Кроме того отметим, что l.end() указывает
не на последний элемент списка, а на элемент после последнего, что важно (и так не только для list, а для всех итераторов). Кроме того, для итераторов важно
использовать операцию префиксного инкремента, так как постфиксный инкремент создает копию, как правило это не нужно.

\subsection{string}
Пример использования:
\begin{lstlisting}
std::string s = "hello";
std::cout << s.size();
s = s + s; //(1)
std::cout << s.c_str(); //(2)
\end{lstlisting}
в (1) происходит конкатенация, а (2) с помощью функции c\_str получаем c-style строку символов. Касательно передачи строк в качестве параметров всегда используйте
ссылку на константу, это никак не помешает, пока не потребуется изменять строку.

\subsection{Нетривиальные примеры работы с контейнерами}

\paragraph{Удаление элементов контейнера удовлетворяющих какому-то условию}
\begin{lstlisting}
C c; //(1)
for (c::iterator it = c.begin(); it != c.end();)
	if (check(*it))
		it = c.erase(it); //(2)
	else
		++it;
\end{lstlisting}
в (1) объявляется контейнер, а в (2) происходит удаление элемента и возвращается итератор на позицию соответсвующую позиции итератора до удаления (т. е. позиция не
меняется при удалении, удалив первый элемент получим итератор на первый элемент измененного списка и т. д.)

Небольшое изменение сделает код неработоспособным в общем случае:
\begin{lstlisting}
C c;
for (c::iterator it = c.begin(); it != c.end(); ++it)
	if (check(*it))
		it = c.erase(it)
\end{lstlisting}

\paragraph{Выбор конкретного контейнера} Есть универсальное правило - используйте вектор всегда, если вы не знаете каких-либо очень серьезных причин использовать
что-то другое.